
Baraj, Ziua 2, Problema 1 (Quadtree)
28.05.1996

	Un quadtree este un format de reprezentare folosit pentru a codifica 
imagini. Ideea fundamentala este aceea ca orice imagine poate fi "sparta" in 
patru patrate. Fiecare patrat poate fi spart la randul lui in patru subpatrate,
 s.a.m.d. In quadtree, imaginea este reprezentata sub forma arborescenta, cu un
nod parinte corespunzator patratului si patru descendenti directi pentru cele 
patru subpatrate in care este "spart"  patratul, luate intr-o ordine predefinita.
	Bineinteles, daca imaginea este monocroma, ea poate fi reprezentata 
printr-un quadtree cu un singur nod. In general, un patrat trebuie divizat numai 
daca are pixeli de culori diferite. Deci, in final quadtree nu va avea o 
adancime uniforma.
	Un artist lucreaza pe calculator cu imagini alb-negru de dimensiune 
32x32 cu un total de 1024 pixeli per imagine. Una din operatiile pe care le 
realizeaza este asamblarea a doua imagini pentru a forma o imagine noua. In 
aceasta imagine rezultata, un pixel este negru daca a fost negru in cel putin 
una din imaginile componente; altfel, pixelul este alb.
	Artistul crede in ceea ce el numeste "umplere preferata": pentru ca o 
imagine sa fie interesanta (adica sa fie ceruta pe piata) cea mai importanta 
proprietate este numarul pixelilor umpluti (negri). Deci, inainte de a asambla 
doua imagini, artistul va dori sa stie cati pixeli negri va avea imaginea 
rezultata. Sarcina este de a scrie un program care, primind reprezentarea a doua 
imagini sub forma de quadtree, va calcula numarul de pixeli negri in imaginea 
care va rezulta prin adunarea celor doua imagini.
Exemplu: Sa presupunem ca ordinea de numarare a subpatratelor care formeaza un 
patrat este: 
				2  1
				3  4
Atunci putem reprezenta o imagine ca suma de doua imagini, atat direct cat si 
ca suma de doi quadtree, astfel (s-a notat cu 0 patratul alb, cu 1 cel negru, 
cu 'o' un nod interior din quadtree):

	1 1 0 0		1 1 0 0		1 1 0 0
	0 0 0 1		1 1 0 0		1 1 0 1
	1 1 0 0    +	0 0 0 0  =		1 1 0 0
	1 1 0 0		0 0 1 0		1 1 1 0

          o                o                       o
      /   |  \ \         //| \                  / |\  \
     /    |  |  \       // |  \                /  | \  \
   o      o  1  0   +  0 1 0   o       =      o   1 1   o
 // \\  // \\                // \\          // \\     // \\
0 0 0 1 11 0 0              0 0 1 0        0 0 0 1   0 0 1 0

Acestea se pot scrie in preordine astfel (e- nod terminal alb, f - nod terminal
negru, p - nod rezultat din combinarea celor patru descendenti):
    ppeeefpffeefe         +    pefepeefe      =       ppeeefffpeefe

Cum imaginea are 32x32=1024 pixeli, fiecare patrat din desen contine 8x8=64 
pixeli. Deci, cum primul desen are 7 patrate negre, el va avea 7X64=448 pixeli 
negri. Din acest punct de vedere, relatia din desen este:
	448               +       320         =             640

Intrare: 
Prima linie de intrare specifica numarul N de cazuri de test. Intrarea pentru  
fiecare fiecare test contine doua linii reprezetand cele doua imagini care se 
asambleaza, cate un sir pe fiecare linie. Sirul da reprezentare in preordine a 
unui quadtree, in care litera 'p' reprezinta un nod parinte, 'f' (full) - un 
patrat negru, iar 'e' (empty) - un patrat alb.
Nu se introduc date de intrare gresite.

Iesire:
Pentru fiecare caz de test se va tipari pe ecran o linie de forma :
"Exista X pixeli negri"
unde X este numarul de pixeli negri din imaginea rezultata.
Exemplu:
Pentru intrarea:
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
   iesirea va fi:
Exista 640 pixeli negri
Exista 512 pixeli negri
Exista 384 pixeli negri
---------------------------------

Baraj, ziua 2, problema 2 (Hasuri)
28.05.1996
  
	Se citesc de la intrare numerele naturale N,K(K<=N<=40). Se considera o
banda de hartie impartita in N casute adiacente. Sunt doua persoane, numite 
jucatorii 1 si 2. Acestia aleg alternativ, incepand cu jucatorul 1, cate o 
secventa de cel putin 1 si cel mult K celule consecutive nehasurate si le 
hasureaza. Castiga jucatorul care efecteaza ultima mutare (hasureaza ultimele 
celule).
  a) Se cere sa se determine daca jucatorul 1 are strategie sigura de castig;
  b) Sa se programeze modul in care actioneaza jucatorul 1, mutarile jucatorului 
2 fiind citite de la tastatura.
Intrare:
  N si K se dau de la tastatura.
Iesire:
a) Un mesaj corespunzator strategiei de castig a jucatorului 1
b) Jucatorul 1 afiseaza o mutare sub forma unei linii
x y
unde x reprezinta pozitia casutei unde va fi prima hasura, iar y numarul de 
casute urmatoare (spre dreapta) care se vor hasura. Intre x si y exista un 
singur spatiu.
Raspunsul de la tastatura al jucatorului 2 se face in aceeasi forma.
	In final, calculatorul va afisa un mesaj de forma:
Jucatorul i a castigat
Exemplu:
Pentru intrarea
4 2
Calculatorul afiseaza:

Jucatorul 1 are strategie de castig

Pentru (b), o varianta de joc este:
2 2  (calculator)
1 1  (tastatura)
4 1  (calculator)

Jucatorul 1 a castigat
-------------------------------------------

Baraj, ziua2, problema 3 (Grasanul)
28.05.1996

	Unii din noi pot fi destul de norocosi ca sa poata trece prin cea mai 
mica gaura; altii nu. Un drum de la A la B intr-un supermarket (chiar fara un 
carucior) poate fi destul de dificil si sa solicite destul de multa abilitate.
Sa consideram intr-un mod abstract aceasta problema a trecerii prin magazin: 
fiind dat un culoar de o anumita largime, cu obstacole imprastiate prin el, 
aratati cum poate o persoana grasa sa-l parcurga intrand prin capatul stang al 
culoarului si iesind prin cel din dreapta. Consideram ca, vazuta de sus, o 
persoana grasa arata ca un cerc, si ca ea este incompresibila (o persoana cu 
diametrul d nu poate trece printre doua obstacole aflate la o distanta mai mica 
dacat d).
Intrare:
  Prima linie a fisierului de intrare GRASAN.INP specifica numarul N de date de 
test care trebuie prelucrate de program. Intrarea pentru fiecare test consta 
din urmatoarele linii:

L W    - L (0<=L<=100) este lungimea culoarului, W (0<=W<=100) - largimea lui;
O      - O (0<=O<=100) reprezinta numarul de obstacole din culoar;
X1 Y1
X2 Y2  - (Xi Yi), 0<=Xi<=L,0<=Yi<=W reprezinta coordonatele unui obstacol
....
XO YO

	Toate datele sunt numere intregi.

Iesire:
Pentru fiecare test se tipareste pe ecran o linie de forma:

"Marimea maxima in testul t este M"

unde t (1<=t<=N) este numarul testului, iar M este un numar real cu 4 cifre
zecimale care da diametrul maxim al unei persoane care poate reusi sa treaca
prin culoar in testul respectiv.

Exemplu: Pentru intrarea:
1
8 5
8
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1

iesirea este:

Marimea maxima in testul 1 este 2.2361

Timp limita pentru fiecare test: 30 secunde

